• Entstehung
• Standard PSO
• Beispiel 2D
• Nebenbedingungen
• Beispiel 2D mit Nebenbedingungen
• Konvergenz
• Vor- und Nachteile
• Fazit

• Erfunden von Russell Eberhardt und James Kennedy in 1995
  

  
• Analogie zu natürlichen Vogelschwärmen
• PSO ist eine naturanaloge Metaheuristik
• Erste Anwendung in der Teilchenphysik

Optimierungsproblem:

• Lösungsraum \(\Omega\) (z.b. \(\mathbb{R}^n\))
• Zielfunktion: \(f: \Omega \rightarrow \mathbb{R}\)
• Gesucht ist \(\omega \in \Omega\) für das \(f(\omega) = min\{f(x)|x \in \Omega\}\) gilt
  
  

Vehalten des PSO:

• Partikel bewegen sich im \(\mathbb{R}^n\) iterativ
• Partikel teilen sich Informationen
• Partikel haben ein Gedächtnis
• Partikel ändern ihren Richtungsvektor abhängig von 3 Faktoren
• Iteriere bis die Abbruchbedingung erreicht ist

1. Initialisiere zufällige Positionen \(x^{k, i}\) und Richtungsvektoren \(v^{k, i}\) der Partikel \(k\) in Iteration \(i=0\)

2. Evaluiere die Kostenfunktion mit der Position jedes Partikels

3. Speicher die bisher beste Position in \(g_{best}^i\)

4. Speicher die bisher beste Position pro Partikel in \(p_{best}^{k,i}\)

5. Iterationsschritt \(i \rightarrow i+1\) pro Partikel \(k\): \[ \begin{aligned} v^{k, i+1} &= w \cdot v^{k, i} + c_p \cdot r_1 \cdot (p_{best}^{k,i}-x^{k,i}) + c_g \cdot r_2 \cdot (g_{best}^{k,i}-x^{k,i}) \\ x^{k, i+1} &= x^{k, i} + v^{k, i+1} \end{aligned} \]

6. Wiederhole Schritt 2-5 bis die Abbruchbedingung erreicht ist

Zielfunktion:
\[ \begin{aligned} f(x, y) =& -20\cdot e^{-0.2 \cdot \sqrt{0.5 \cdot ((x-1)^2 + (y-1)^2)}} \\ & \ - e^{0.5 \cdot ( cos(2\cdot \pi \cdot x) + cos(2\cdot \pi \cdot y))} + e + 20 \end{aligned} \] Aufgabe:
Minimiere \(f(x,y)\) mit \(-10 \leq x \leq 10\) und \(-10 \leq y \leq 10\)

PSO App

Beispiele:

• Summe soll 100% ergeben
• Summe der Gewichte von Elementen mit Ausprägung A soll weniger als 20% betragen
• Kosten sollen kleiner als 100 Euro sein
• Weniger als 20 Elemente sollen ungleich Null sein
• …

Methoden:

• Penalty
• Verwerfen von ungültigen Lösungen
• Reparieren von ungültigen Lösungen

Alte Zielfunktion: \(f(x)\) mit \(f: \mathbb{R}^n \rightarrow \mathbb{R}\)

Bruch von Nebenbedingungen: \(g(x)\) mit \(g(x) \geq 0 \ \forall x \in \mathbb{R}^n\)

Neue Zielfunktion: \(z(x) = f(x) + g(x)\)

Beispiel für gängige Nebenbedingungen: \[ A^T \times x \geq b_0 \] Dann könnte \(g(x)\) wie folgt aussehen: \[ g(x) = ||\vec{\lambda}( A^T \times x - b_0 )||_2^2 \] mit elementweiser Anwendung von \[ \lambda(x) = \begin{cases} 0 &\text{ if }x \geq 0\\ x &\text{ if }x < 0 \end{cases} \]

Gomez and Levy function (modified)

wiki constrained tests problems

PSO App

Convergence Analysis for Particle Swarm Optimization (von Berthold Schmitt)

“Obwohl das PSO in zahlreichen realen Anwendungen verwendet wird, haben theoretische Betrachtungen bisher nur einige wenige Teilaspekte des Algorithmus erklärt. Ein solcher Aspekt, mit dem sich viele Wissenschaftler auseinandersetzen, ist das Phänomen der Konvergenz des Partikelschwarms. Das bedeutet, dass die Partikel gegen einen Punkt im Suchraum konvergieren. Insbesondere konnten notwendige und hinreichende Bedingungen an die Schwarmparameter ermittelt werden, unter denen Konvergenz gewährleistet ist. Allerdings ist bis jetzt kein theoretisches Resultat über die Qualität dieses Grenzwertes bekannt, das für den unmodizierten PSO-Algorithmus in einer allgemeineren Situation als beispielsweise nur für genau eine Zielfunktion bewiesen werden konnte.”

• Alles stark simplifiziert: Standard PSO und \(p_{best}=g_{best}=const\)
• Es kann gezeigt werden, das folgende Terme fast sicher konvergieren: \(\lim\limits_{n \rightarrow \infty}E(X^n)=\mu\) und \(\lim\limits_{n \rightarrow \infty}Var(X^n) = \sigma^2\)
• Es kann keine Aussage über die Qualität dieses Grenzwertes gemacht werden.
• Es kann bewiesen werden, das wenn der Schwarm im \(\mathbb{R}\) konvergiert, das es fast sicher ein locales Minimum ist.

• Konstantes \(p_{best}=5\) und \(g_{best}=7\)
• Partikel sind unabhängig
• Hyperparameter \(w=0.3\), \(c_p=1\), \(c_g=1\)
• Initialisierte Position und Richtungsvektor \(X^0=V^0=0\)

\(f=\) 0.9033333

Nachteile:

• keine Garantie für die Qualität der Lösung
• Hyperparameter
• zusätzliche Information über das explizite Problem kann nur schwer berücksichtigt werden
  
  

Vorteile:

• ist sehr effizient implementierbar (kleine Datenstruktur und nur Basis-Operatoren)
• simple Anwendbar auch bei komplexen Problemen und Nebenbedingungen
• kann diskrete Probleme lösen
• es gibt viele Varianten, die deutlich besser sind als das Standard PSO
• Allzweck-Werkzeug für Optimierungsprobleme